package com.dyz.leetcode;

public class PathSum437 {
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null){return 0;}
        //从根节点开始向下或者从其他节点开始向下
        return dfs(root, targetSum)+pathSum(root.left, targetSum) + pathSum(root.right, targetSum);


    }
    private int dfs(TreeNode root, int targetSum){
        if(root==null){return 0;}
        //以当前节点作为起始节点让路径和先归零，重新开始向下找路径和是否与targetSum匹配
        int result = 0;
        if(root.val==targetSum){ result++;}
        //探索当前节点向下所有子树，targetSum与对应值做差，递归到两者相等记录找到一条路径，探底后马上收敛
        result += dfs(root.left, targetSum-root.val) + dfs(root.right, targetSum-root.val);

        return result;
    }
}
